/**
 * 
 */
package it.uniroma3.dia.digraph.algorithm.utility.kouterplanar;

import it.uniroma3.dia.digraph.algorithm.kouterplanar.kouterplanar.KouterplanarNode;
import it.uniroma3.dia.digraph.algorithm.utility.AngleManager;
import it.uniroma3.dia.digraph.algorithm.utility.Utility;

import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.graphdrawing.graphml.xmlns.GraphType;
import org.graphdrawing.graphml.xmlns.NodeType;

/**
 * @author Cionzo
 *
 */
public class Peeler {
	
	
	private static AngleManager angleComparator = Utility.getAngleComparator();
	
	public static Map<Integer, List<NodeType>> decomposeToLayers(GraphType graph){
		int currentDepth = 0;
		// the map to be returned
		Map<Integer, List<NodeType>> depth2nodes = new HashMap<Integer, List<NodeType>>();
		
		// the adjacency matrix
		Map<String, Set<String>> adjMatrix = Utility.buildAdjacencyMatrix(graph);
		
		//the map id-> node
		Map<String, NodeType> nodeMap = Utility.extractNodes(graph);

		// a list with the nodes of the graph 
		List<NodeType> nodes = new LinkedList<NodeType>();
		nodes.addAll(graph.getNodeCollection().getNode());
		
		List<NodeType> currentBoundary;
		
		while(! nodes.isEmpty()){
			currentBoundary = getBoundaryNodes(nodes, adjMatrix, nodeMap);
			depth2nodes.put(currentDepth++, currentBoundary);
			clean(nodes, adjMatrix, currentBoundary);
		}
		
		return depth2nodes;
	}
	
	/**
	 * Returns a list with the nodes on the outer face of the graph
	 * @param nodes the nodes of the graph
	 * @param adjMatrix an adjacency matrix for the nodes of the graph
	 * @param nodeMap a map id->node
	 * @return the nodes on the boundary of the graph
	 */
	public static List<NodeType> getBoundaryNodes(List<NodeType> nodes, Map<String, Set<String>> adjMatrix, Map<String, NodeType> nodeMap){
		List<NodeType> boundary = new LinkedList<NodeType>();
		
		if (nodes.isEmpty())
			return boundary;
		
		NodeType first, current, previous, next;
		first = findBottomRight(nodes);
		previous = first;
		current = first;
		next = findNextOnBoundary(previous, first, adjMatrix, nodeMap);
		boundary.add(first);
		
		while (next!=null && ! next.equals(first)){
//			System.out.println("c: "+current+" p:"+previous+" n"+next);	//TODO: levami
//			System.out.println("c: "+current);
//			Utility.printNodeCollection(boundary);
//			System.out.println();
			boundary.add(next);
			current = next;
			next = findNextOnBoundary(previous, current, adjMatrix, nodeMap);
			previous = current;
//			System.out.println(boundary);
		}
		
//		System.out.println("\n\n final boundary:");
//		Utility.printNodeCollection(boundary);
//		System.out.println("-----------------");
		
		
		return boundary;
	}
	
	
	
	public static NodeType findNextOnBoundary(NodeType previous, NodeType current, Map<String, Set<String>> adjMatrix, Map<String, NodeType> nodeMap){
		List<NodeType> neighbors = getNeighborsList(current, adjMatrix, nodeMap);
		angleComparator.setOrigin(current);
		int nextIndex;
		Collections.sort(neighbors, angleComparator);
		//		Utility.log("Peeler.nextOnBoundary()", previous, current, neighbors); //TODO levami
		if (neighbors.size()!=0) {
		    nextIndex = neighbors.indexOf(previous);
		    nextIndex++;
		    nextIndex = nextIndex % neighbors.size();
		    return neighbors.get(nextIndex);
		}
		return null;
	}

	



	private static List<NodeType> getNeighborsList(NodeType current,
			Map<String, Set<String>> adjMatrix, Map<String, NodeType> nodeMap) {
		List<NodeType> neighbors = new LinkedList<NodeType>();
//		System.out.println("neighbor list for: "+current); //TODO:levami
		for (String neighId : adjMatrix.get(current.getId()))
			neighbors.add(nodeMap.get(neighId));
		
		return neighbors;
	}



	private static NodeType findBottomRight(List<NodeType> nodes) {
		Collections.sort(nodes, new Comparator<NodeType>() {

			@Override
			public int compare(NodeType o1, NodeType o2) {
				
				if (o1.getY() < o2.getY())
					return -1;
				if (o1.getY() > o2.getY())
					return 1;
				
				return (int) Math.signum(o1.getX() - o2.getX());
				
				
			}
		});
		
		return nodes.get(0);
	}
	
	/**
	 * Clears the adjacency matrix and the "to-classify" node list
	 * by removing any reference to classified nodes
	 * 
	 * @param toClassify a list containing the nodes of the graph
	 * @param adjMatrix an adjacency matrix for the graph to peel
	 * @param nodesOnCurrentLayer a list containing the nodes classified as laying on current level
	 */
	private static void clean(List<NodeType> toClassify,
			Map<String, Set<String>> adjMatrix,
			List<NodeType> nodesOnCurrentLayer) {
		
//		printlayer(nodesOnCurrentLayer);
		
		Set<String> neighborsId;
		
		for (NodeType current : nodesOnCurrentLayer){			
			toClassify.remove(current);
			
			//remove the row for the current node
			neighborsId = adjMatrix.remove(current.getId());
			
			//remove this node from the neighbors of its inner-level neighbors
			for (String neighborId  : neighborsId)
				adjMatrix.get(neighborId).remove(current.getId());
			
		}
		
	}

	/**
	 * @param parents
	 * @return
	 */
	public static void sortByCCW(List<KouterplanarNode> parents) {
	    
	    
	    throw new RuntimeException("Peeler"+".sortByCCW()"+" not yet implemented");
	}

}
